package com.loriot.common.separate_squares_i_3453;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * @Title: Main
 * @Package: com.loriot.common.separate_squares_i_3453
 * @Description:
 * @Author: zzy boy
 * @Date: 2025/10/23 9:32
 * @Version: 0.0.1-alpha
 */

public class Main {
    // 通过二分查找进行计算
    class Solution1 {
        public double separateSquares(int[][] squares) {
            // 计算正方形最高的y
            int maxY = 0;
            // 正方形的面积之和
            long sumS = 0;
            for(int[] item:squares){
                int y0 = item[1];
                int l = item[2];
                maxY = Math.max(maxY,y0+l);
                sumS+=(long)l*l;
            }
            /*
             * 开始二分
             */
            // 最多计算60次，就可以使得right-left<10^-5
            int k = 60;
            double left = 0;
            double right =(double) maxY;
            while(k-->0){
                // 计算mid
                double mid = right+(left-right)/2;
                // 查看 y=mid的下方正方形面积 >= y=mid上方正方形面积
                if(isBottomSBig(squares,mid,sumS)){
                    right = mid;
                }
                else{
                    left = mid;
                }
                // 满足条件就直接返回
                if(right-left<Math.pow(10, -5))return left;
            }
            return (left + right) / 2;
        }
        // 查看y以下的面积是否大于y以上的面积，需要这里的=和上面对于right与left的修改有相关性
        // 能够决定找到最小的y坐标还是最大的y坐标
        boolean isBottomSBig(int[][] squares,double y, long sumS){
            double bottomS = 0;
            for(int[] item:squares){
                int y0 = item[1];
                int l = item[2];
                // 线在底边以上
                if(y>y0){
                    bottomS+=l*Math.min(y-y0,l);
                }
            }
            return bottomS>=sumS-bottomS;
        }
    }


    class Solution2 {
        public double separateSquares(int[][] squares) {
            long totArea = 0;
            TreeMap<Integer, Long> diff = new TreeMap<>();
            for (int[] sq : squares) {
                int y = sq[1];
                long l = sq[2];
                totArea += l * l;
                int start = y;
                int end = y+(int)l;
                diff.merge(start, l, Long::sum);
                diff.merge(end, -l, Long::sum);
            }

            long area = 0;
            long sumL = 0;
            int preY = 0; // 不好计算下一个 y，改成维护上一个 y
            for (Entry<Integer, Long> e : diff.entrySet()) {
                int y = e.getKey();
                area += sumL * (y - preY); // 底边长 * 高 = 新增面积
                // 如果y下方的面积已经超过总面积一半
                if (area * 2 >= totArea) {
                    // 返回 y- 超过的面积/底边长
                    return y - (area * 2 - totArea) / (sumL * 2.0);
                }
                // 跳到下一个位置
                preY = y;
                // 当前没有封口的底边
                sumL += e.getValue(); // 矩形底边长度之和
            }
            return -1;
        }
    }
}
